home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / programr / eckelt01.zip / 14 / SORTED.H < prev    next >
C/C++ Source or Header  |  1995-02-23  |  4KB  |  120 lines
  1. // File from page 618 in "Thinking in C++" by Bruce Eckel
  2. //////////////////////////////////////////////////
  3. // From the compressed package ECKELT01.ZIP 2/21/95
  4. // Copyright (c) Bruce Eckel, 1995 
  5. // Source code file from the book "Thinking in C++", 
  6. // Prentice Hall, 1995, ISBN: 0-13-917709-4
  7. // All rights reserved EXCEPT as allowed by the following 
  8. // statements: You may freely use this file for your own 
  9. // work, including modifications and distribution in 
  10. // executable form only. You may copy and distribute this 
  11. // file, as long as it is only distributed in the complete 
  12. // (compressed) package with the other files from this 
  13. // book and you do not remove this copyright and notice. 
  14. // You may not distribute modified versions of the source 
  15. // code in this package. This package may be freely placed 
  16. // on bulletin boards, internet nodes, shareware disks and 
  17. // product vendor disks. You may not use this file in 
  18. // printed media without the express permission of the 
  19. // author. Bruce Eckel makes no 
  20. // representation about the suitability of this software 
  21. // for any purpose. It is provided "as is" without express 
  22. // or implied warranty of any kind. The entire risk as to 
  23. // the quality and performance of the software is with 
  24. // you. Should the software prove defective, you assume 
  25. // the cost of all necessary servicing, repair, or 
  26. // correction. 
  27. // If you think you've found an error, please 
  28. // email all modified files with loudly commented changes 
  29. // to: eckel@aol.com (please use the same 
  30. // address for non-code errors found in the book).
  31. //////////////////////////////////////////////////
  32.  
  33. //: SORTED.H -- Template inheritance
  34. #ifndef SORTED_H_
  35. #define SORTED_H_
  36. #include <stdlib.h>
  37. #include <string.h>
  38. #include <time.h>
  39. #include "..\14\tstash.h"
  40. #include "..\14\set.h"
  41.  
  42. template<class T>
  43. class sorted :  public tstash<T> {
  44.   void bubblesort();
  45. public:
  46.   int add(T* element) {
  47.     tstash<T>::add(element);
  48.     bubblesort();
  49.     return 0; // Sort moves the element
  50.   }
  51. };
  52.  
  53. template<class T>
  54. void sorted<T>::bubblesort() {
  55.   for(int i = count(); i > 0; i--)
  56.     for(int j = 1; j < i; j++)
  57.       if(*storage[j-1] > *storage[j]) {
  58.         // Swap the two elements:
  59.         T* t = storage[j-1];
  60.         storage[j-1] = storage[j];
  61.         storage[j] = t;
  62.       }
  63. }
  64.  
  65. // Quick & dirty sorted set:
  66. template<class T>
  67. class sortedSet : public set<T> {
  68.   sorted<T> Sorted;
  69. public:
  70.   void add(T& e) {
  71.     if(contains(e)) return;
  72.     set<T>::add(e);
  73.     Sorted.add(new T(e));
  74.   }
  75.   T& operator[] (int index) {
  76.     assert(index >= 0 && index < length());
  77.     assert(Sorted[index]);
  78.     return *Sorted[index];
  79.   }
  80.   int length() {
  81.     return Sorted.count();
  82.   }
  83. };
  84.  
  85. // Unique random number generator:
  86. template<int upper_bound>
  87. class urand {
  88.   int map[upper_bound];
  89.   int recycle;
  90. public:
  91.   urand(int Recycle = 0);
  92.   int operator()();
  93. };
  94.  
  95. template<int upper_bound>
  96. urand<upper_bound>::urand(int Recycle = 0)
  97.   : recycle(Recycle) {
  98.   memset(map, 0, upper_bound * sizeof(int));
  99.   // Seed the random number generator:
  100.   time_t t;
  101.   srand((unsigned)time(&t));
  102. }
  103.  
  104. template<int upper_bound>
  105. int urand<upper_bound>::operator()() {
  106.   if(!memchr(map, 0, upper_bound)) {
  107.     if(recycle)
  108.       memset(map, 0,
  109.              sizeof(map) * sizeof(int));
  110.     else
  111.       return -1; // No more spaces left
  112.   }
  113.   int newval;
  114.   while(map[newval = rand() % upper_bound])
  115.     ; // Until unique value is found
  116.   map[newval]++; // Set flag
  117.   return newval;
  118. }
  119. #endif // SORTED_H_
  120.